First of all, the terms used in this specification for describing the present invention are as follows:
(1) State: a state is defined by the properties or attributes of DES and defines the behaviour of DES. The state of DES changes to others. DES should be in any state at any point of time.
As an example, CD player powered on has “playing”, “stopped”, etc. and is in any one of those states at any point of time.
(2) Immediate sub-state: The conception of state is hierarchical. Any state can have a number of subordinate states. Those subordinate states are called immediate sub-states.
As an example of CD player, “playing” and “stopped” are immediate sub-states of “power-on”.
(3) Immediate super-state: Contrary conception of immediate sub-state.
As an example of CD player, “power-on” is immediate super-state of “playing” and “stopped”. Immediate super-state is abstracted conception of immediate sub-state representing immediate sub-state. “Playing” state of CD player is thus “power-on” state.
(4) Sub-state: Extended conception of immediate sub-state. Sub-state includes immediate sub-state and all the subordinate states of the immediate sub-state.
(5) Super-state: Extended conception of immediate super-state. Super-state includes immediate super-state and all the superior states of the immediate super-state.
(6) Sibling state: Sibling states have identical immediate super-state.
As an example of CD player, “playing” and “stopped” are sibling states that have identical immediate super-state or “power-on”.
(7) Hierarchical depth: The number of super-states.
(8) Active state: The state where DES currently stays. The other states are referred to inactive states. Active state is also called current state.
(9) State transition: The transference of DES active state from one to another.
(10) Event: The change occurred inside/outside of DES and affecting DES. An event is input of DES and concrete phenomenon that generates output and state change of DES.
(11) Guard condition: Guard condition determines allowance of state transition.
(12) Action: The event that DES generates when state transition occurs. Action is output of DES.
(13) State Transition Diagram (STD): Diagram proposed by Moore and Mealy representing transitive relationship between states.
(14) State Chart: Extended type of STD proposed by David Harel. Hierarchical structure is added to Moore and Mealy's STD so that parallel state or orthogonality can be represented.
(15) Transition-allowed state: Transition-allowed states are ones to which current state is allowed to transfer to.
FIG. 1 is flowchart of development process of Discrete Event System
As shown in FIG. 1, the process of developing DES generally comprises “REQUIERMENT AND SPECIFICATION” step for describing the functions of DES (S101), “ANALYSIS AND DESIGN” step for modelling the DES according to the requirement and specification (S103), “IMPLEMENTATION” step for implementing the result of modelling (S105), and “VERIFICATION” step for verifying the DES (S107).
The process of developing DES generally iterates several times until the DES satisfies the requirement and specification. The process of developing DES is repeated from the “REQUIERMENT AND SPECIFICATION” step (S101) if an error is detected or the DES needs change of function.
The “ANALYSIS AND DESIGN” step (S103) has sub steps of “DESCRIPTION OF SYSTEM”, “ASCERTAINMENT OF ELEMENTS”, “DESCRIPTION OF RELATIONSHIP OF ELEMENTS” and “MODELLING OF DYNAMIC BEHAVIOUR”.
The present invention is provided with a method for designing and implementing Discrete Event System (DES) and more particularly deals with a method for describing and implementing dynamic behaviour of DES, this method needed in the step of “ANALYSIS AND DESIGN” step (S103).
FIGS. 2A and 2B show the characteristics of non-state system and state system.
DES is system where response of DES is triggered by the occurrence of event(s). DES is classified into non-state system and state system.
Non-state system, as shown in FIG. 2A, has output dependent only upon input and its behaviour is relatively simple. I is set of input ij of DES, O is set of output Ok of DES, S is set of state Sl of DES, and f is output function.
State system, as shown in FIG. 2B, has output dependent upon both input and state of DES and its behaviour is relatively complicate. State system needs the sub step of “MODELLING OF DYNAMIC BEHAVIOUR”. Function g is state function.
Distinction between non-state system and state system is apparent from FIGS. 2A and 2B.
As shown in FIGS. 2A and 2B, it is ascertainment of output function f(•) that is needed in modelling non-state system because there is only relationship “Ok=f(i)” in non-state system. Thus, modelling non-state system is relatively simple process requiring only the relationship between input and output.
On the other hand, most real-world systems are state systems. The output function f(•) of state system needs state variable Sl that is current state, that is, state variable Sl is needed for determining output Ok. Next state Sx is determined by state function Sx=g(ij, Sl).
The degree of difficulty in modelling state system is much higher than the degree of difficulty in modelling non-state system because of description of state change.
FIG. 3 illustrates requirement and specification of CD player; FIG. 4 shows events, actions and states extracted from the requirement and specification of FIG. 3; FIG. 5 is State Transition Diagram modelled by the requirement and specification of FIG. 3; and FIG. 6 is State Chart modelled by the requirement and specification of FIG. 3.
There are State Transition Diagram (STD) proposed by Moore and Mealy and State Chart (SC) proposed by David Harel for representing state change (Refer to FIGS. 5 and 6).
STD represents transition between states and is drawn on flatly. Input event ij generating state transition is generally marked on STD.
State transition process of STD is as follows:                (1) Event occurs;        (2) Guard condition is tested; and        (3) State transition is executed on the condition that the guard condition is satisfied.        
Exit action of current state, state change, and entry action of the target state are sequentially performed in execution of state transition.
As an example of CD player, FIG. 4 shows input (I, event)/output (O, action)/states (S) ascertained from the given requirement and specification of FIG. 3.
FIG. 5 shows STD drawn by the input (I, event)/output (O, action)/states (S) of FIG. 4. Default state 501 is initial state or sub-state that the CD player automatically enters when the CD player enters arbitrary state.
STD was not utilised widely even though STD visually represents transition relationship between states to improve efficiency of modelling because of flat structure having the shortcoming that flat structure cannot represent complicate transition relationship between states.
Harel's SC overcomes the shortcoming of STD. SC can represent hierarchical state transition relationship. Any state of SC can have a number of subordinate sub-states in itself, which is generalised type of state diagram.
FIG. 6 shows SC drawn by the input (I, event)/output (O, action)/states (S) of FIG. 4.
As an example of CD player shown in FIG. 6, states of “Stopped” (503) and “Playing” (505) are possible only when the CD player is powered on and state of “Power On” (601) can be abstracted from the states of “Stopped” (503) and “Playing” (505). The states of “Stopped” (503) and “Playing” (505) thus become sub-states of the state of “Power On” (601), and the state of “Power On” (601) becomes super-state of the states of “Stopped” (503) and “Playing” (505).
The step of “Stopped” (503) is default state of the step of “Power On” (601) because the CD player automatically enters the step of “Stopped” (503).
Harel's SC is implemented on the commercial software ┌STATEMATE┘ of ┌I-Logix┘, ┌BetterState┘ of ┌MatrixX┘, and ┌Stateflow┘ of ┌Matlab┘ for visual modelling of DES using the concept of SC.
Commercial software ┌Rapid┘ of ┌Emultek┘ for designing man-machine interface also uses similar concept but has distinction that SC is of tree structure on the ground that SC has hierarchical structure(The referred name of software and/or company may be the registered trademark held by that company).
Modelling DES by methodology of SC is known to have advantage of DES implementation, modification and extension due to exact description of DES dynamic behaviour.
But it is difficult to model DES by methodology of SC. Modelling DES by methodology of SC fundamentally requires exact ascertainment of DES states. There is quite a possibility that inconceivable modelling flaw may exist and the result of modelling DES by methodology of SC can vary with designers because of abstractness of conception “state”.
It is difficult for non-expert to model DES by methodology of SC and different DES model of SC can result by different view of experts.
CD player is very simple system with only three (3) states and can be modelled by different view as shown in FIGS. 5 and 6.
An abstract characteristic of conception “state” also makes modification and extension of already completed DES model complicated.
FIG. 7 illustrates requirement and specification with pause function added to the requirement and specification of FIG. 3; FIG. 8 shows events, actions and states extracted from the requirement and specification of FIG. 7; and FIGS. 9A to 9C show three (3) types of State Charts different to one another and modelled by the requirement and specification of FIG. 7.
Requirement and specification and event/action/states of FIGS. 3 and 7 differs from each other in that CD player of state “play” after “stop” plays tracks from the first track and CD player of state “play” after “paused” plays tracks of former position.
The following is illustrating various modelling according to designer:
Modelling I defines “Paused” as sub-state of “Stopped” (503);
Modelling II defines “Paused” as sub-state of “Playing” (505); and
Modelling III defines “Paused” as sibling state of “Stopped” (503) and “Playing” (505).
FIGS. 9A to 9C respectively show SCs corresponding to Modelling I/II/III.
It is difficult to determine which model is better in that efficiency of model is determined by purpose or implementation of DES. But different model from identical DES decrease efficiency of development when men cooperate in development. Consistency of development is also decreased because of different view of identical designer as the case may be.
To overcome the problem of abstractness in conventional SC, Message Sequence Chart (MSC) of International Telecommunication Union (ITU) and ┌Cult3D┘ of ┌Cycore┘ were proposed to stress characteristic of event.
Messages of MSC are the entire communication phenomenon including data transfer and function call and can be treated as events. MSC is structural method describing data flow by dealing with message transference between components of which DES comprises.
Sequence Diagram and Collaboration Diagram of UML (Unified Modelling Language) similar to MSC use the same concept and can be considered as slightly modified type of MSC.
But there is defect that MSC cannot describe control flow controlling entire DES including data transference or behaviour in component itself in that MSC just describes data transference.
┌Cult3D┘, different from MSC, describes behaviour of DES. But ┌Cult3D┘ can describe behaviour of only non-state system and thus cannot describe state dependant behaviour. That is, there is a weak point that ┌Cult3D┘ describes relationship of input and output by Ok=f(ij), ignoring state change and cannot describe dynamic behaviour of DES.
The following is references that aid in understanding the present invention:
1) David Harel, “State charts, a visual approach to complex systems”, Science of Computer Programming, 1987;
2) David Harel, “On Visual Formalism”, Communication of the ACM, pp 514–530, May 1988;
3) David Harel, “STATEMATE: A Working Environment for Development of Complex Reactive System”, IEEE Transaction on Software Engineering, pp 403–414, April 1997;
4) D. Coleman, F. Hayes and S. Bear, “Introducing object charts or how to use state charts in object-oriented design”, IEEE Transactions on software engineering, vol. 18, no. 1, pp. 9–18, January 1992;
5) D. Budgen, “Software Design”, Addison Wesley, pp 123–135, 1994;
6) Antti Auer, “State Testing of Embedded Software, University of Oulu, Department of Information Processing Science and Infotech Oulu, Research paper series A2T, March 1997;
7) P. Ramadge and W. M. Wonham, “The Control of Discrete Event Systems”, Proceedings of the IEEE, Vol 77, No. 1, 1989;
8) Quatrani, Terry., “Visual Modeling with Rational Rose and UML”, Addison Wesley, 1998;
9) Gomaa, Hassan., “Software Design Methods for Concurrent and Real-Time Systems”, Addison Wesley, 1993; and
10) ITU (International Telecommunication Union), “ITU-T Recommendation Z.120—Message Sequence Chart”, ITU, November 1999.